6286. Mysterious equation
Little Vasya is very fond of
equations. Once his sight caught the equation x + y + xy = n. Vasya
wants to know the number of pairs of non-negative integers x and y, that are the solutions of this equation.
Input. One
integer n (0 ≤
n ≤ 109).
Output. Print the number of
pairs of solutions.
|
Sample input |
Sample output |
|
5 |
4 |
SOLUTION
number
theory
Algorithm analysis
Write the equation in the form
(x + 1)(y +
1) = n + 1
The
number of its solutions equals to the
number of divisors of the number n + 1. If d is a divisor of n + 1, then one of solutions of equation can be found from the system
If
we denote by d(n) the number of
divisors of the number n, then the answer to the problem will be the value d(n + 1).
Example
Let n = 5, consider the equation x + y + xy = 5. Rewrite it in the
form
(x + 1)(y +
1) = 6
Number 6 has d(6) = d(21 * 31) = 2 * 2 = 4 divisors (they are 1, 2, 3, 6). To find all solutions
to the equation, 4 systems of equations should be solved:
, 
,
,
The solutions are the pairs (x, y): (0, 5), (1,
2), (2, 1), (5, 0).
Algorithm realization
Function CountDivisors computes the number of divisors of n.
int CountDivisors(int n)
{
int c, i, res = 1;
for (i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
c = 0;
while (n % i == 0) n /= i, c++;
res *= (c + 1);
}
}
if (n > 1) res *= 2;
return res;
}
Read the input value of n.
scanf("%d", &n);
Print the number of divisors of
number n + 1.
printf("%d\n", CountDivisors(n + 1));